/**
 * COMP9414 13s1			Assignment 3			Marco Pricone z3452265
 * 
 * This is an implementation of a model-based agent which plays the Rogue text-based game.
 * A model-based agent has a perception module which is used to choose actions only based on what it currently observes,
 * and a world model which records the present and the past world observations and is used to take decisions based on all observations made.
 * In our case, the current observation of the world is the 24-characters matrix view received at each call
 * of the get_action method.
 *  
 * The agent explores the world through its 24-characters matrix view (which represents the agent's sensor in the model)
 * and builds a world model saving each view in a big world matrix. In case the agent has got either a key or an axe,
 * when it perceives a tree or a door in the front of him, the agent automatically chops the tree or opens the door. This mechanism of
 * automatically acting without considering the world model but just the current view helps a lot when considering a cell either walkable
 * or not. In fact, if the agent holds a key, it will see any cell containing a door as walkable, since the perception mechanism
 * will automatically open the door once the agent will be in the front of it. The same apply for trees when the agent holds an axe, that is
 * every tree cell in the world model will be considered as a walkable cell cause the perception mechanism will automatically chop
 * any tree in front of the agent.
 * If the agent does not see any tool available to catch in the world model, it starts exploring the map, walking on the 
 * unexplored walkable cells.
 * If a tool is detected in the world model, and the agent finds a walkable path from the current position to the tool's cell,
 * it goes there and catch the tool.
 * The agent uses the A* algorithm to search for a least cost path from one position to another, either in case is going to catch a tool or when it's
 * just exploring the map and going to an unexplored cell.
 * A path from one position to another consists of several moves, which in turn consists of several actions.
 * Moves belonging to a path are saved in a stack and read each time the previous move is completed.
 * Action to be taken are saved in a buffer queue and read at each time get_action method is called, after the perception module
 * has checked the cell ahead.
 * The method moveToAdjacentCell adds actions on the actions buffer, while A* path-finding method adds moves on the moves stack.
 * Each move in the stack will eventually become a call of moveToAdjacentCell method, which transform a move in a series of action to be taken.
 *  
 */

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.net.Socket;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class Agent {

	private final static int MAX_WORLD_MODEL_SIZE = 200;
	private final static int VIEW_SIZE = 5;

	private final static char NORTH_DIRECTION = '^';
	private final static char WEST_DIRECTION = '<';
	private final static char EAST_DIRECTION = '>';
	private final static char SOUTH_DIRECTION = 'v';

	private final static char FORWARD_ACTION = 'F';
	private final static char TURN_LEFT_ACTION = 'L';
	private final static char TURN_RIGHT_ACTION = 'R';
	private final static char CHOP_ACTION = 'C';
	private final static char OPEN_DOOR_ACTION = 'O';
	private final static char BLAST_ACTION = 'B';
	private final static char START_READING_ACTIONS_BUFFER = 0;
	private final static char NO_ACTION = 0;

	private final static char TREE_OBSTACLE_CELL = 'T';
	private final static char DOOR_OBSTACLE_CELL = '-';
	private final static char WALL_OBSTACLE_CELL = '*';
	private final static char WATER_OBSTACLE_CELL = '~';

	private final static char AXE_TOOL_CELL = 'a';
	private final static char KEY_TOOL_CELL = 'k';
	private final static char DYNAMITE_TOOL_CELL = 'd';
	private final static char GOLD_TOOL_CELL = 'g';

	private final static char FREE_CELL = ' ';
	private final static char UNKNOWN_CELL = '?';

	private final static int DIRECT_NODE_WALK_COST = 10;
	private final static int DIAGONAL_NODE_WALK_COST = 14;

	private char worldModel[][] = new char[MAX_WORLD_MODEL_SIZE][MAX_WORLD_MODEL_SIZE];
	private char currentDirection;
	private int xInitialPos, yInitialPos;
	private int xCurrentPos, yCurrentPos;

	private boolean hasAxe;
	private boolean hasKey;
	private boolean hasGold;
	private int numOfDynamites;

	private Queue<Action> actionsBuffer;
	private Stack<AStarNode> movesStack;
	private List<Target> targetList;
	private List<Target> reachedTargetList;
	private List<AStarNode> nodesAlreadyExplored;

	public Agent(){

		//agent's state initialization
		for(int i=0;i<MAX_WORLD_MODEL_SIZE;i++){
			for(int j=0;j<MAX_WORLD_MODEL_SIZE;j++){			
				worldModel[i][j] = UNKNOWN_CELL;
			}
		}
		currentDirection = SOUTH_DIRECTION;
		xCurrentPos = MAX_WORLD_MODEL_SIZE/2;
		yCurrentPos = MAX_WORLD_MODEL_SIZE/2;
		xInitialPos = xCurrentPos;
		yInitialPos = yCurrentPos;
		hasAxe = false;
		hasKey = false;
		hasGold = false;
		numOfDynamites = 0;

		actionsBuffer = new LinkedList<Action>();
		movesStack = new Stack<AStarNode>();
		targetList = new ArrayList<Target>();
		reachedTargetList = new ArrayList<Target>();
		nodesAlreadyExplored = new ArrayList<AStarNode>();

	}


	public char get_action( char view[][] ) {

		add_view_to_world_model(view);
		//print_world_model();
		//print_view(view);

		// If we want to be able to see the agent moving in the map,
		// a delay must be inserted at each get_action call.
		try {
			Thread.sleep(25);
		} catch (InterruptedException ie) {}

		// We first call the perception module which must take first priority decisions.
		// In our case, these will be a chop tree or a open door action. 
		// Doing so, we are able to consider tree or door cells as walkable, if the agent holds the right tool.
		char perceptiveAction = checkPerception(view);
		if(perceptiveAction!=NO_ACTION)
			return perceptiveAction;

		// Then we read the actions buffer, which contains a series of actions to be taken
		// in order to move from one cell to another.
		if(!actionsBuffer.isEmpty()){
			Action nextAction = actionsBuffer.remove();
			calculateNextState(nextAction.getAction(),view);
			return nextAction.getAction();
		}

		// When a move is completed (actions buffer is empty) we go on with the next move
		// waiting for being executed in the moves stack.
		while(!movesStack.isEmpty()){
			AStarNode currentMove = movesStack.pop();
			if(currentMove.isToBlast()){
				moveToAdjacentCell(currentMove.getxPos(),currentMove.getyPos(),true);
				numOfDynamites--;
			} else {
				moveToAdjacentCell(currentMove.getxPos(),currentMove.getyPos(),false);
			}
			return START_READING_ACTIONS_BUFFER;
		}

		// After all moves in the buffer are executed, we check whether the gold cell
		// has been found. If so, we start reading again the actions buffer, otherwise we go on.
		boolean goldFound = checkGold();
		if(goldFound){
			return START_READING_ACTIONS_BUFFER;
		}

		// If gold has not been found, we check whether a tool cell
		// has been found. If so, we start reading again the actions buffer, otherwise we go on.
		boolean targetFound = checkForReachableTargets();
		if(targetFound){
			return START_READING_ACTIONS_BUFFER;
		}

		// If no gold or tool cell has been found in the world model,
		// we start exploring the world until a tool is found.
		// If we can't reach any other tool exploring the whole walkable map, the agent will block.
		exploreMap();
		return START_READING_ACTIONS_BUFFER;

	}

	/**
	 * This method is called right after the perception method and before any other method, and it checks
	 * whether the agent has already taken the gold or a gold cell is reachable in the world model.
	 * In the first case, A* path-finding method is called from the current position to the initial position
	 * and the game is won. In the second case, A* path-finding is called and the agent is sent to
	 * the cell which contains the gold. After that, the first part of the method will send the agent to the 
	 * initial position and the game is won. In these two cases, the method returns true. Otherwise,
	 * if the agent has no gold or gold is not reachable in the world mode. the method returns false.
	 * @return
	 */

	private boolean checkGold(){
		if(hasGold){
			movesStack = aStarPathfinding(xCurrentPos,yCurrentPos,xInitialPos,yInitialPos);
			return true;
		}

		for(Target target:targetList){
			if(target.getTargetType()==GOLD_TOOL_CELL){
				movesStack = aStarPathfinding(xCurrentPos,yCurrentPos,target.getxPos(),target.getyPos());
				if(!movesStack.isEmpty())
					return true;
			}
		}
		return false;
	}

	/**
	 * This method is called at each get_action call to check whether there are reachable targets in the world model.
	 * If yes, the method first tries to get any axe of key, in order not to use dynamites if there's a path to reach them
	 * without needing to blast any cell. If there are no reachable axes or keys, the algorithm checks whether there are
	 * reachable dynamites in the world model. If a target is reachable, A* path-finding method is called which
	 * fills the moves stack and true is returned. If there are no reachable targets detected, false is returned.
	 * @return
	 */
	private boolean checkForReachableTargets(){

		List<Target> axesAndKeys = new ArrayList<Target>();
		List<Target> dynamites = new ArrayList<Target>();
		for(Target currentTarget: targetList){
			if(currentTarget.getTargetType()==AXE_TOOL_CELL || currentTarget.getTargetType()==KEY_TOOL_CELL){
				axesAndKeys.add(currentTarget);
			} else if(currentTarget.getTargetType()==DYNAMITE_TOOL_CELL){
				dynamites.add(currentTarget);
			}
		}

		Stack<AStarNode> pathToTarget = new Stack<AStarNode>();
		Target target = null;

		for(Target currentTarget: axesAndKeys){
			pathToTarget = aStarPathfinding(xCurrentPos,yCurrentPos,currentTarget.getxPos(),currentTarget.getyPos());
			if(!pathToTarget.isEmpty()){
				target = currentTarget;
				break;
			}
		}
		if(!pathToTarget.isEmpty()){
			movesStack = pathToTarget;
			targetList.remove(target);
			reachedTargetList.add(target);
			return true;
		}

		for(Target currentTarget: dynamites){
			pathToTarget = aStarPathfinding(xCurrentPos,yCurrentPos,currentTarget.getxPos(),currentTarget.getyPos());
			if(!pathToTarget.isEmpty()){
				target = currentTarget;
				break;
			}
		}
		if(!pathToTarget.isEmpty()){
			movesStack = pathToTarget;
			targetList.remove(target);
			reachedTargetList.add(target);
			return true;
		}
		return false;
	}

	/**
	 * This method explores the map when no targets (tools or gold) are detected in the world model.
	 * When the agent walks to a cell, the cell is set as "already explored" and it is added on a list
	 * called nodesAlreadyExplored. The algorithm checks all the cells nearby the current position and if
	 * one of these is walkable, it sends the agent there. If no walkable cells are found, the exploring range
	 * is doubled and the algorithm repeats. During the method execution the algorithm tries to find a path
	 * only once per cell, saving on a list all nodes for which the A* algorithm returned an empty moves stack.
	 * This method will block the agent in case all the walkable cells have been visited and no more unexplored walkable cells 
	 * are left when the exploring range has its maximum value. 
	 * In that case the agent is not able to win the game, as a path to any target is never found.
	 * 
	 */

	private void exploreMap(){

		int exploringRange = 2;
		List<AStarNode> evaluatedCells = new ArrayList<AStarNode>();
		while(exploringRange<=MAX_WORLD_MODEL_SIZE/2+1){
			for(int xStep=-exploringRange;xStep<=2*exploringRange+1;xStep++){
				for(int yStep=-exploringRange;yStep<=2*exploringRange+1;yStep++){
					AStarNode nodeToExplore = new AStarNode(xCurrentPos+xStep,yCurrentPos+yStep);
					if(!evaluatedCells.contains(nodeToExplore)){
						if(!nodesAlreadyExplored.contains(nodeToExplore)){
							movesStack = aStarPathfinding(xCurrentPos,yCurrentPos,xCurrentPos+xStep,yCurrentPos+yStep);
						}
						if(!movesStack.isEmpty()){
							return;
						} else {
							evaluatedCells.add(nodeToExplore);
						}
					}
				}
			}
			exploringRange*=2;
		}
	}

	/**
	 * This method implements the A* path-finding algorithm, which finds a least cost path through cells,
	 * from the starting position to the target position. A node of type AStarNode represents a cell in the 
	 * world model. Only walkable cells or cells which can be blast are evaluated during the algorithm execution.
	 * The AStarNode class models a cells storing its position, type, and the number of dynamites left 
	 * in a path from the start position to the cell itself.
	 * Since this algorithm is used both to find a path to real targets (tools or gold cells) and to find a path to an unexplored
	 * cells, we don't want to use dynamites when just exploring the map to get on an unexplored free cell. We avoid
	 * this by checking the target type: if the target is a tool or a gold cell, we are allowed to use dynamites;
	 * if the target is just an explored walkable cell, we decide to save resources setting the number of dynamites available to the 
	 * algorithm to zero.
	 * During the algorithm execution, we keep two lists of nodes, a open list and closed list.
	 * The closed list contains nodes which have already been chosen as belonging to the least cost
	 * path to destination.
	 * The open list contains all the nodes already evaluated but not chosen yet or not to be chosen. Among these nodes
	 * at each algorithm step we choose the node with least cost F = G + H, where G is the cost required
	 * to get to that node from the starting node, and H is the value of the heuristic function evaluated
	 * for the current node by the calculateHeuristics method, which estimates the cost of getting to destination from the current cell. 
	 * Among the nodes in the open list,at each step we choose the node with minimum cost F, we remove it from the open list and we add it 
	 * to the closed list of nodes that don't need to be analyzed anymore.
	 * The algorithm ends either when the open list is empty (no path has been found to destination) or
	 * when the target node is added to the closed list(a path has been found and can be saved going
	 * backwards, from the target node go from each node to its parent until reaching the starting node).
	 * 
	 * The algorithm goes as follow:
	 * 
	 * 1) Add the starting node to the open list;
	 * 
	 * 2) Repeat the following:
	 * 	
	 * 		a) Look for the lowest F cost node on the open list. We now call this node 
	 * 			the current node.
	 * 	
	 * 		b) Switch it to the closed list.
	 * 		
	 * 		c) For each of the 8 nodes adjacent to the current node:
	 * 
	 * 			I) If it's not walkable or it's already on the closed list,
	 * 				ignore it. Otherwise do the following.
	 * 			II) If it's not on the open list, add it to the open list. Make the current node
	 * 				the parent of this node. Calculate the F,G, and H costs of the node.
	 * 			III) If it's already on the open list, check to see whether this path to that
	 *  			node is better, using G cost as the measure. A lower G cost means that this is 
	 * 				a better path. If so, change the parent of the node to the current node, and 
	 * 				recalculate the G and F costs of the node.
	 * 
	 * 		d) Stop when:
	 * 
	 * 			I) Add the target node to the closed list, in which case the path
	 * 				has been found, or
	 * 			II) Fail to find the target node, and the open list is empty. In this case
	 * 				there is no path to the desired target node.
	 * 
	 * 3) Save the path. From the target node, go backwards from each node to its parent node until
	 * 		reaching the starting node. The path is saved as a stack of nodes (movesStack), being the top of
	 * 		the stack an adjacent node of the starting node. The get_action method will move
	 * 		 from adjacent cell to adjacent cell, calling the moveToAdjacentCell method until reaching
	 * 		the target node.
	 * 
	 * 
	 * 
	 * @param startX
	 * @param startY
	 * @param targetX
	 * @param targetY
	 * @return
	 */

	private Stack<AStarNode> aStarPathfinding(int startX,int startY,int targetX,int targetY){

		//create a new stack of nodes
		Stack<AStarNode> movesStack = new Stack<AStarNode>();
		//if the target cell is not walkable, return an empty stack
		if(!isCellWalkable(targetX,targetY)){
			return movesStack;
		}
		//create open and closed list, and initialize the starting node
		List<AStarNode> openList = new ArrayList<AStarNode>();
		List<AStarNode> closedList = new ArrayList<AStarNode>();
		AStarNode startNode = new AStarNode(startX,startY);
		AStarNode targetNode = new AStarNode(targetX,targetY);
		startNode.setG(0);
		startNode.setH(calculateHeuristics(startX,startY,targetX,targetY));

		//check whether it is worth to use dynamites along the path, based on the target type
		char target = worldModel[targetY][targetX];
		if(target==DYNAMITE_TOOL_CELL || target==AXE_TOOL_CELL || target==KEY_TOOL_CELL || target==GOLD_TOOL_CELL){
			startNode.setNumOfDynamitesLeft(numOfDynamites);
		} else {
			startNode.setNumOfDynamitesLeft(0);
		}

		//we recognize the root node of the tree as the node who points itself in the parent field
		startNode.setParent(startNode);

		//add the starting node to the open list
		openList.add(startNode);

		//repeat until either the target node is on the closed list or the open list is empty
		while(!closedList.contains(targetNode) && !openList.isEmpty()){

			//select the node with minimum F on the open list; we call this nodeMinF.
			AStarNode nodeMinF = null;
			int currentMin = Integer.MAX_VALUE;
			for(AStarNode node: openList){
				if(node.getF()<=currentMin){
					nodeMinF = node;
					currentMin = node.getF();
				}
			}

			//switch nodeMinF to the closed list
			openList.remove(nodeMinF);
			closedList.add(nodeMinF);

			// here we calculate the position of the diagonal adjacent cells, labeled as follow:

			//	|A|B|C|	
			// 	|D| |E|
			// 	|F|G|H|

			int xA =nodeMinF.getxPos()-1;
			int yA =nodeMinF.getyPos()-1;
			int xC =nodeMinF.getxPos()+1;
			int yC =nodeMinF.getyPos()-1;
			int xF =nodeMinF.getxPos()-1;
			int yF =nodeMinF.getyPos()+1;
			int xH =nodeMinF.getxPos()+1;
			int yH =nodeMinF.getyPos()+1;

			// we check the 8 adjacent nodes
			for(int y=nodeMinF.getyPos()-1;y<=nodeMinF.getyPos()+1;y++){
				for(int x=nodeMinF.getxPos()-1;x<=nodeMinF.getxPos()+1;x++){

					//we consider a cell only if it is walkable or can be blast
					if(isCellWalkable(x,y) || isCellBlastable(x,y,nodeMinF.getNumOfDynamitesLeft())){	
						AStarNode nodeXY = new AStarNode(x,y);

						//we consider a cell only if has not been already added to the closed list
						// we then set or update costs G and H 
						if(!closedList.contains(nodeXY)){
							int nodeXYWalkCost;
							if((x==xA && y==yA) || (x==xC && y==yC) || (x==xF && y==yF) || (x==xH && y==yH)){
								if(!isCellDiagonallyReachable(nodeMinF.getxPos(),nodeMinF.getyPos(),x,y))
									continue;				
								nodeXYWalkCost = DIAGONAL_NODE_WALK_COST;
							} else {
								nodeXYWalkCost = DIRECT_NODE_WALK_COST;
							}
							if(isCellBlastable(x,y,nodeMinF.getNumOfDynamitesLeft())){
								nodeXY.setNumOfDynamitesLeft(nodeMinF.getNumOfDynamitesLeft()-1);
								nodeXY.setToBlast(true);
							} else {
								nodeXY.setNumOfDynamitesLeft(nodeMinF.getNumOfDynamitesLeft());
								nodeXY.setToBlast(false);
							}
							nodeXY.setG(nodeMinF.getG()+nodeXYWalkCost);
							nodeXY.setH(calculateHeuristics(x,y,targetX,targetY));

							if(!openList.contains(nodeXY)){
								openList.add(nodeXY);
								nodeXY.setParent(nodeMinF);		
							} else {
								AStarNode oldNodeXY = openList.get(openList.indexOf(nodeXY));
								if(nodeXY.getG()<oldNodeXY.getG()){
									oldNodeXY.setG(nodeXY.getG());
									oldNodeXY.setParent(nodeMinF);
								}
							}


						}//end_if
					}//end_if
				}//end_for
			}//end_for
		}//end_while

		//if the while loop breaks without finding any path, we return an empty stack...
		if(openList.isEmpty() && !closedList.contains(targetNode)){
			return movesStack;

		}

		// ... otherwise we go backwards from each node to its parent until the root node is reached,
		// pushing the nodes on the stack, and return the stack.
		AStarNode cursorNode = closedList.get(closedList.indexOf(targetNode));
		while(cursorNode.getParent()!=cursorNode){
			movesStack.push(cursorNode);
			cursorNode = cursorNode.getParent();
		}

		return movesStack;

	}

	/**
	 * This method calculates the heuristic function used in A* algorithm.
	 * The heuristics estimates the cost of getting to the destination target as the direct distance in the
	 * world model from the current position to the target (as done with Romania map at lectures).
	 * The cost of walking to an adjacent non-diagonal cell is set to 10, while the cost of walking
	 * to a diagonal adjacent cell is set to 14 (which approximates the value of 10*sqrt(2).
	 * This heuristics is also admissible since it never overestimates the real walking distance to the target.
	 * The path found by the A* algorithm will thus be optimal.
	 * @param currentX
	 * @param currentY
	 * @param targetX
	 * @param targetY
	 * @return
	 */

	private int calculateHeuristics(int currentX,int currentY,int targetX,int targetY){

		int xDistance = Math.abs(currentX-targetX);
		int yDistance = Math.abs(currentY-targetY);
		double distance = DIRECT_NODE_WALK_COST * Math.sqrt(xDistance^2+yDistance^2);
		return (int) distance;
	}

	/**
	 * This method translates the command of moving to any position cell adjacent 
	 * to the current cell in the world model into a series of elementary actions required to do such a move.
	 * These actions will change depending on the current direction and on which of the 8 possible cells
	 * we wish to move. The method checks whether the destination cell is actually adjacent and if it is 
	 * also walkable. If these constraints are met, the series of actions required to move to the desired cell
	 * are inserted into the actions buffer, which will be read at the next call of get_action method.
	 * The method also takes into account whether the destination cell is to blast or not, inserting
	 * a blast action before forwarding to the destination cell if needed. 
	 * Some line in the method's code contains a commented letter A,B,C,D,E,F,G, or H. This letter represents
	 * which adjacent cell the portion of the code is related to, as in the following schema:
	 * 
	 *  	|A|B|C|		|A|B|C|		|A|B|C|		|A|B|C|
	 *  	|D|^|E|		|D|<|E|		|D|>|E|		|D|v|E|
	 *  	|F|G|H|		|F|G|H|		|F|G|H|		|F|G|H|
	 *  
	 *  The agent stands in the center of the square, and the letters refer to an absolute direction in the world model,
	 *  with no care about the agent's direction. Of course, the agent's actual direction will be taken into account
	 *  in the switch-case statement to choose the proper sequence of actions required to move to any of the adjacent cells.
	 *  For the diagonal cells, we have two ways of getting there. If both ways require walking on a non-walkable cell, the agent
	 *  won't move and a error message is printed on screen (it never happens when the agent plays the game, as the A* algorithm
	 *  does not send the agent in a cell which requires to pass through a non-walkable cell to be reached).
	 * 
	 */
	private void moveToAdjacentCell(int xPos,int yPos, boolean isToBlast){

		if(Math.abs(xCurrentPos-xPos)+Math.abs(yCurrentPos-yPos)>2){
			return;
		}
		if(!isCellWalkable(xPos,yPos) && !isToBlast){
			movesStack.clear();
			return;
		}

		switch(currentDirection){

		case NORTH_DIRECTION: 
			if(xPos==xCurrentPos-1 && yPos==yCurrentPos-1){//A

				if(isCellWalkable(xCurrentPos-1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos,yCurrentPos-1)){
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else{
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos && yPos==yCurrentPos-1){//B

				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	

			} else if(xPos==xCurrentPos+1 && yPos==yCurrentPos-1){//C

				if(isCellWalkable(xCurrentPos+1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos,yCurrentPos-1)){
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos-1 && yPos==yCurrentPos){//D
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if(xPos==xCurrentPos+1 && yPos==yCurrentPos){//E
				actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if(xPos==xCurrentPos-1 && yPos==yCurrentPos+1){//F

				if(isCellWalkable(xCurrentPos-1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos,yCurrentPos+1)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos && yPos==yCurrentPos+1){//G
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if((xPos==xCurrentPos+1 && yPos==yCurrentPos+1)){//H

				if(isCellWalkable(xCurrentPos+1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos,yCurrentPos+1)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}
			}
			break;
		case SOUTH_DIRECTION: 
			if(xPos==xCurrentPos-1 && yPos==yCurrentPos-1){//A

				if(isCellWalkable(xCurrentPos-1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos,yCurrentPos-1)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos && yPos==yCurrentPos-1){//B
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if(xPos==xCurrentPos+1 && yPos==yCurrentPos-1){//C

				if(isCellWalkable(xCurrentPos+1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos,yCurrentPos-1)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos-1 && yPos==yCurrentPos){//D
				actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if(xPos==xCurrentPos+1 && yPos==yCurrentPos){//E
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if(xPos==xCurrentPos-1 && yPos==yCurrentPos+1){//F

				if(isCellWalkable(xCurrentPos-1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos,yCurrentPos+1)){
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos && yPos==yCurrentPos+1){//G
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if((xPos==xCurrentPos+1 && yPos==yCurrentPos+1)){//H

				if(isCellWalkable(xCurrentPos+1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos,yCurrentPos+1)){
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else{
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			}
			break;

		case EAST_DIRECTION: 
			if(xPos==xCurrentPos-1 && yPos==yCurrentPos-1){//A

				if(isCellWalkable(xCurrentPos,yCurrentPos-1)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos-1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos && yPos==yCurrentPos-1){//B
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if(xPos==xCurrentPos+1 && yPos==yCurrentPos-1){//C

				if(isCellWalkable(xCurrentPos,yCurrentPos-1)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos+1,yCurrentPos)){
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else{
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos-1 && yPos==yCurrentPos){//D
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if(xPos==xCurrentPos+1 && yPos==yCurrentPos){//E
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if(xPos==xCurrentPos-1 && yPos==yCurrentPos+1){//F

				if(isCellWalkable(xCurrentPos,yCurrentPos+1)){
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos-1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos && yPos==yCurrentPos+1){//G
				actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if((xPos==xCurrentPos+1 && yPos==yCurrentPos+1)){//H

				if(isCellWalkable(xCurrentPos,yCurrentPos+1)){
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos+1,yCurrentPos)){
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			}
			break;

		case WEST_DIRECTION: 
			if(xPos==xCurrentPos-1 && yPos==yCurrentPos-1){//A

				if(isCellWalkable(xCurrentPos,yCurrentPos-1)){
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos-1,yCurrentPos)){
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos && yPos==yCurrentPos-1){//B
				actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if(xPos==xCurrentPos+1 && yPos==yCurrentPos-1){//C

				if(isCellWalkable(xCurrentPos,yCurrentPos-1)){
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos+1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos-1 && yPos==yCurrentPos){//D
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if(xPos==xCurrentPos+1 && yPos==yCurrentPos){//E
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if(xPos==xCurrentPos-1 && yPos==yCurrentPos+1){//F

				if(isCellWalkable(xCurrentPos,yCurrentPos+1)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos-1,yCurrentPos)){
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else{
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}

			} else if(xPos==xCurrentPos && yPos==yCurrentPos+1){//G
				actionsBuffer.add(new Action(TURN_LEFT_ACTION));
				if(isToBlast){
					actionsBuffer.add(new Action(BLAST_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
				} else {
					actionsBuffer.add(new Action(FORWARD_ACTION));
				}	
			} else if((xPos==xCurrentPos+1 && yPos==yCurrentPos+1)){//H

				if(isCellWalkable(xCurrentPos,yCurrentPos+1)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else if(isCellWalkable(xCurrentPos+1,yCurrentPos)){
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(TURN_LEFT_ACTION));
					actionsBuffer.add(new Action(FORWARD_ACTION));
					actionsBuffer.add(new Action(TURN_RIGHT_ACTION));
					if(isToBlast){
						actionsBuffer.add(new Action(BLAST_ACTION));
						actionsBuffer.add(new Action(FORWARD_ACTION));
					} else {
						actionsBuffer.add(new Action(FORWARD_ACTION));
					}	
				} else {
					System.out.println("Cannot move to an adiacent cell through an unwalkable cell");
				}
			}
			break;
		}
	}

	/**
	 * This method tests whether a cell in a given position in the world model is walkable or not.
	 * First of all, if the given cell position exceeds the admissible range of matrix's indexes, the
	 * method returns trivially false.
	 * A position(cell) in the world model will be considered as walkable if and only if the cell is
	 * either a free cell, an axe tool cell, a key tool cell, a dynamite cell, a gold cell, or any tree or door cells
	 * if the agent has the respective removal tool.
	 * In all other cases, namely a wall cell, a water cell, a still unknown cell, a tree cell(if agent does not hold an axe),
	 * or a door cell (if agent does not hold a key), the method will returns false.
	 * 
	 * @param xPos
	 * @param yPos
	 * @return
	 */
	private boolean isCellWalkable(int xPos, int yPos){


		if(xPos>=MAX_WORLD_MODEL_SIZE || yPos>=MAX_WORLD_MODEL_SIZE || xPos<0 || yPos<0)
			return false;

		if(worldModel[yPos][xPos]==FREE_CELL || worldModel[yPos][xPos]==AXE_TOOL_CELL || worldModel[yPos][xPos]==KEY_TOOL_CELL
				|| worldModel[yPos][xPos]==DYNAMITE_TOOL_CELL || worldModel[yPos][xPos]==GOLD_TOOL_CELL)
			return true;

		if(hasAxe && hasKey){
			if(worldModel[yPos][xPos]==TREE_OBSTACLE_CELL || worldModel[yPos][xPos]==DOOR_OBSTACLE_CELL){
				return true;
			}
		} else if(hasAxe && !hasKey){
			if(worldModel[yPos][xPos]==TREE_OBSTACLE_CELL){
				return true;
			}
		}else if(!hasAxe && hasKey){
			if(worldModel[yPos][xPos]==DOOR_OBSTACLE_CELL){
				return true;
			}
		}

		return false;
	}

	/**
	 * 
	 * This method tests whether a cell which is diagonally adjacent to the agent's current position is actually
	 * reachable without trying to walk through a non-walkable cell. The method is used by the A* path-finding
	 * algorithm to ignore walkable diagonal cells which are not actually reachable from the current 
	 * evaluated previous cell in the path without trying to walk on a non-walkable cell.
	 * @param startX
	 * @param startY
	 * @param targetX
	 * @param targetY
	 * @return
	 */
	private boolean isCellDiagonallyReachable(int startX,int startY,int targetX,int targetY){

		int xDistance = Math.abs(startX-targetX);
		int yDistance = Math.abs(startY-targetY);

		if(xDistance==1 && yDistance==1){

			int xOffset = targetX-startX;
			int yOffset = targetY-startY;

			if(xOffset==-1 && yOffset==-1){
				if(isCellWalkable(startX-1,startY) || isCellWalkable(startX,startY-1))
					return true;
			} else if(xOffset==1 && yOffset==-1){
				if(isCellWalkable(startX+1,startY) || isCellWalkable(startX,startY-1))
					return true;
			} else if(xOffset==-1 && yOffset==1){
				if(isCellWalkable(startX-1,startY) || isCellWalkable(startX,startY+1))
					return true;
			} else if(xOffset==1 && yOffset==1){
				if(isCellWalkable(startX+1,startY) || isCellWalkable(startX,startY+1))
					return true;
			}	
		}

		return false;
	}

	/**
	 * 
	 * This method tests whether a cell in a given position in the world model can be blasted or not.
	 * If there are no dynamites available the method returns trivially false. Otherwise it checks
	 * the cell type and returns true if and only if the cell is a tree, a wall or a door.
	 * @param xPos
	 * @param yPos
	 * @param numOfDynamitesLeft
	 * @return
	 */
	private boolean isCellBlastable(int xPos,int yPos, int numOfDynamitesLeft){

		if(numOfDynamitesLeft<=0)
			return false;

		if(worldModel[yPos][xPos]==TREE_OBSTACLE_CELL || worldModel[yPos][xPos]==WALL_OBSTACLE_CELL
				|| worldModel[yPos][xPos]==DOOR_OBSTACLE_CELL)
			return true;

		return false;
	}

	/**
	 * This method calculates the next agent's position and direction in the world model, based on the current chosen action and
	 * the current direction. This method allows the agent to track the result of its actions in the world model.
	 * For example, if the agent is currently pointing towards the south direction, and the chosen action is to turn left, the agent automatically
	 * knows that the next direction will be east. Also, if the chosen action is forward, and the agent knows it can go forward as the method
	 * isForwardAllowed returned true, then it updates the current position to the next position based also on the current direction.
	 * This method also makes the agent aware of whether it has taken a new tool. This happens when the agent is going forward and the cell ahead
	 * contains a new tool.
	 * @param action
	 * @param view
	 */

	private void calculateNextState(char action, char[][] view){

		switch (currentDirection){
		case NORTH_DIRECTION: 
			if(action==TURN_RIGHT_ACTION){
				currentDirection = EAST_DIRECTION;
			} else if(action==TURN_LEFT_ACTION){
				currentDirection = WEST_DIRECTION;
			} else if(action==FORWARD_ACTION && isForwardAllowed(view)){
				yCurrentPos--;
			}
			break;
		case EAST_DIRECTION: 
			if(action==TURN_RIGHT_ACTION){
				currentDirection = SOUTH_DIRECTION;
			} else if(action==TURN_LEFT_ACTION){
				currentDirection = NORTH_DIRECTION;
			} else if(action==FORWARD_ACTION && isForwardAllowed(view)){
				xCurrentPos++;
			}
			break;
		case SOUTH_DIRECTION: 
			if(action==TURN_RIGHT_ACTION){
				currentDirection = WEST_DIRECTION;
			} else if(action==TURN_LEFT_ACTION){
				currentDirection = EAST_DIRECTION;
			} else if(action==FORWARD_ACTION && isForwardAllowed(view)){
				yCurrentPos++;
			}
			break;
		case WEST_DIRECTION: 
			if(action==TURN_RIGHT_ACTION){
				currentDirection = NORTH_DIRECTION;
			} else if(action==TURN_LEFT_ACTION){
				currentDirection = SOUTH_DIRECTION;
			} else if(action==FORWARD_ACTION && isForwardAllowed(view)){
				xCurrentPos--;
			}
			break;
		}

		if(action==FORWARD_ACTION && isForwardAllowed(view)){

			char cellAhead = view[VIEW_SIZE/2-1][VIEW_SIZE/2];

			switch (cellAhead){

			case AXE_TOOL_CELL: hasAxe = true; break;
			case KEY_TOOL_CELL: hasKey = true;  break;
			case GOLD_TOOL_CELL: hasGold = true;  break;
			case DYNAMITE_TOOL_CELL: numOfDynamites++; break;

			}
		}

	}

	/**
	 * This method tests whether forward action is allowed. It will be allowed only if the cell ahead is a free cell or a cell
	 * with a tool. It is assumed that the perception module has properly removed any removable obstacle before hand if it was possible, 
	 * making the cell ahead a free cell.
	 * In any case, if the cell ahead is an obstacle (water, wall, tree or a door) the method returns false. 
	 * @param view
	 * @return
	 */

	private boolean isForwardAllowed(char view[][]){

		char cellAhead = view[VIEW_SIZE/2-1][VIEW_SIZE/2];

		if(cellAhead==FREE_CELL || cellAhead==AXE_TOOL_CELL || cellAhead==KEY_TOOL_CELL 
				|| cellAhead==DYNAMITE_TOOL_CELL || cellAhead==GOLD_TOOL_CELL)
			return true;

		return false;

	}

	/**
	 * 
	 * This method implements the perception module of the model-based agent. It tests whether the cell in the front
	 * of the agent is either a tree of a door. If the cell ahead is a tree and the agent holds an axe, the method returns
	 * a chop action. If the cell ahead is a door and the agent holds a key, the method returns an open door action.
	 * In all the other cases, the method returns the NO_ACTION character '?' which is not recognized as a valid action, so it is suitable
	 * for being utilized as a no action character.
	 * @param view
	 * @return
	 */

	private char checkPerception(char[][] view){

		char cellAhead = view[VIEW_SIZE/2-1][VIEW_SIZE/2];

		if(cellAhead==TREE_OBSTACLE_CELL && hasAxe)
			return CHOP_ACTION;
		if(cellAhead==DOOR_OBSTACLE_CELL && hasKey)
			return OPEN_DOOR_ACTION;

		return NO_ACTION;
	}


	void print_view( char view[][] )
	{
		int i,j;

		System.out.println("\n+-----+");
		for( i=0; i < 5; i++ ) {
			System.out.print("|");
			for( j=0; j < 5; j++ ) {
				if(( i == 2 )&&( j == 2 )) {
					System.out.print('^');
				}
				else {
					System.out.print( view[i][j] );
				}
			}
			System.out.println("|");
		}
		System.out.println("+-----+");
	}

	/**
	 * This method adds the current matrix view to the world model matrix. Depending on the initial direction of
	 * the agent (which is assumed to me always south before this first call of get_action method) and on how many 
	 * times the agent has changed direction, the current view matrix is rotated 1, 2 or 3 times counterclockwise and 
	 * then superimposed on the world model matrix around the current agent position in the world model.
	 * @param view
	 */
	private void add_view_to_world_model(char view[][]){

		char[][] rotatedView = new char[VIEW_SIZE][VIEW_SIZE];

		switch(currentDirection){

		case NORTH_DIRECTION: 
			rotatedView = view;
			break;

		case WEST_DIRECTION:
			rotatedView = turn_view_right(view);
			break;

		case SOUTH_DIRECTION:
			rotatedView = turn_view_right(turn_view_right(view));
			break;

		case EAST_DIRECTION:
			rotatedView = turn_view_right(turn_view_right(turn_view_right(view)));
			break;
		}

		int n = 0;
		int m = 0;

		for(int i = (yCurrentPos - VIEW_SIZE/2); i < (yCurrentPos + VIEW_SIZE/2 + 1);i++){		
			for(int j = (xCurrentPos - VIEW_SIZE/2); j < (xCurrentPos + VIEW_SIZE/2 + 1);j++){
				worldModel[i][j] = rotatedView[n][m];

				char currentCell = worldModel[i][j];
				if(currentCell==AXE_TOOL_CELL || currentCell==KEY_TOOL_CELL 
						|| currentCell==DYNAMITE_TOOL_CELL || currentCell==GOLD_TOOL_CELL){
					Target target = new Target(currentCell,j,i);
					if(!targetList.contains(target) && !reachedTargetList.contains(target))
						targetList.add(target);
				}
				if(i==yCurrentPos && j==xCurrentPos){
					AStarNode node = new AStarNode(j,i);
					if(!nodesAlreadyExplored.contains(node))
						nodesAlreadyExplored.add(node);
				}
				m++;
			}	
			m=0;
			n++;
		}

		// Here we try to speed up the map exploring phase. When all the outer border cells in the view
		// are walkable, the agent sets the inner cell as being already explored and so that he will
		// need to explore only the 4 outer cells at the corners.
		boolean isFastExploringAllowed = true;
		for(int j=xCurrentPos-VIEW_SIZE/2;j<(xCurrentPos + VIEW_SIZE/2 + 1);j++){
			if(!isCellWalkable(j,yCurrentPos-VIEW_SIZE/2)){
				isFastExploringAllowed = false;
				break;
			}	
		}
		for(int j=xCurrentPos-VIEW_SIZE/2;j<(xCurrentPos + VIEW_SIZE/2 + 1);j++){
			if(!isCellWalkable(j,yCurrentPos+VIEW_SIZE/2)){
				isFastExploringAllowed = false;
				break;
			}	
		}
		for(int i=yCurrentPos-VIEW_SIZE/2;i<(yCurrentPos + VIEW_SIZE/2 + 1);i++){
			if(!isCellWalkable(xCurrentPos-VIEW_SIZE/2,i)){
				isFastExploringAllowed = false;
				break;
			}	
		}
		for(int i=yCurrentPos-VIEW_SIZE/2;i<(yCurrentPos + VIEW_SIZE/2 + 1);i++){
			if(!isCellWalkable(xCurrentPos+VIEW_SIZE/2,i)){
				isFastExploringAllowed = false;
				break;
			}	
		}

		if(isFastExploringAllowed){

			for(int i = (yCurrentPos - VIEW_SIZE/2); i < (yCurrentPos + VIEW_SIZE/2+1);i++){		
				for(int j = (xCurrentPos - VIEW_SIZE/2); j < (xCurrentPos + VIEW_SIZE/2+1);j++){
					if(!((i==yCurrentPos-VIEW_SIZE/2 && j==xCurrentPos-VIEW_SIZE/2) || (i==yCurrentPos-VIEW_SIZE/2 && j==xCurrentPos+VIEW_SIZE/2)
							|| (i==yCurrentPos+VIEW_SIZE/2 && j==xCurrentPos-VIEW_SIZE/2) || (i==yCurrentPos+VIEW_SIZE/2 && j==xCurrentPos+VIEW_SIZE/2))){
						AStarNode node = new AStarNode(j,i);
						if(!nodesAlreadyExplored.contains(node))
							nodesAlreadyExplored.add(node);
					}
				}
			}
		}

	}

	/**
	 * 
	 * This method rotates the view received in the get_action method to the counterclockwise. It will be used
	 * by the add_viw_to_world_model method when adding the view to the world model.
	 * @param view
	 * @return
	 */
	private char[][] turn_view_right(char view[][]){

		char newView[][] = new char[VIEW_SIZE][VIEW_SIZE];

		for(int i=0;i<VIEW_SIZE;i++){
			for(int j=0;j<VIEW_SIZE;j++){

				newView[i][j] = view[j][VIEW_SIZE-1-i];
			}
		}
		return newView;

	}

	/**
	 * 
	 * This method prints on screen the world model matrix.
	 */
	private void print_world_model(){

		for(int i=0; i < MAX_WORLD_MODEL_SIZE; i++ ) {
			System.out.print("|");
			for(int j=0; j < MAX_WORLD_MODEL_SIZE; j++ ) {
				System.out.print(worldModel[i][j]);
			}
			System.out.println("|");
		}

	}

	/**
	 * This private class represent an action and contains just a character field. The actions buffer
	 *  will store the sequence of action objects related to a movement from one cell to another in a buffer,
	 *  which is read by the get_action method until it becomes empty.
	 * @author Marco
	 *
	 */

	private class Action {

		private char action;

		public Action(){

		}
		public Action(char action){
			this.action=action;
		}

		public char getAction() {
			return action;
		}

		public void setAction(char action) {
			this.action = action;
		}
	}

	/**
	 * This private class represents a tree node for the A* algorithm which is utilized to find the least cost
	 * path from the current position to the target (which could be either a target object or a walkable cell in case 
	 * the agent is just exploring the map.
	 * @author Marco
	 *
	 */

	private class AStarNode {

		private AStarNode parent;
		private int xPos,yPos;
		private int g,h;

		private int numOfDynamitesLeft;
		private boolean isToBlast;

		public AStarNode(int xPos, int yPos){
			this.setxPos(xPos);
			this.setyPos(yPos);
		}
		public AStarNode(){}

		public AStarNode getParent() {
			return parent;
		}
		public void setParent(AStarNode parent) {
			this.parent = parent;
		}
		public int getxPos() {
			return xPos;
		}
		public void setxPos(int xPos) {
			this.xPos = xPos;
		}
		public int getyPos() {
			return yPos;
		}
		public void setyPos(int yPos) {
			this.yPos = yPos;
		}
		public int getH() {
			return h;
		}
		public void setH(int h) {
			this.h = h;
		}
		public int getG() {
			return g;
		}
		public void setG(int g) {
			this.g = g;
		}
		public int getF() {
			return g+h;
		}
		public boolean equals(Object o){
			if(o instanceof AStarNode){
				AStarNode toCompare = (AStarNode) o;
				if(this.xPos==toCompare.getxPos() && this.yPos==toCompare.getyPos()){
					return true;
				}
			}
			return false;
		}
		public int getNumOfDynamitesLeft() {
			return numOfDynamitesLeft;
		}
		public void setNumOfDynamitesLeft(int numOfDynamitesLeft) {
			this.numOfDynamitesLeft = numOfDynamitesLeft;
		}
		public boolean isToBlast() {
			return isToBlast;
		}
		public void setToBlast(boolean isToBlast) {
			this.isToBlast = isToBlast;
		}
	}

	/**
	 * This private class represents a target cell (e.g an axe, a dynamite, a key or gold).
	 * The agent will keep track of every target he finds on each current view in a target list. When the target
	 * is taken the agent switch the target object to the list of targets which are already taken (reachedTargetsList).
	 * 
	 * @author Marco
	 *
	 */
	private class Target {

		private char targetType;
		private int xPos;
		private int yPos;

		public Target(){

		}
		public Target(char targetType,int xPos, int yPos){
			this.setTargetType(targetType);
			this.setxPos(xPos);
			this.setyPos(yPos);
		}
		public char getTargetType() {
			return targetType;
		}
		public void setTargetType(char targetType) {
			this.targetType = targetType;
		}
		public int getxPos() {
			return xPos;
		}
		public void setxPos(int xPos) {
			this.xPos = xPos;
		}
		public int getyPos() {
			return yPos;
		}
		public void setyPos(int yPos) {
			this.yPos = yPos;
		}
		public boolean equals(Object o){
			if(o instanceof Target){
				Target toCompare = (Target) o;
				if(this.xPos==toCompare.getxPos() && this.yPos==toCompare.getyPos()){
					return true;
				}
			}
			return false;
		}

	}


	public static void main( String[] args )
	{
		InputStream in  = null;
		OutputStream out= null;
		Socket socket   = null;
		Agent  agent    = new Agent();
		char   view[][] = new char[5][5];
		char   action   = 'F';
		int port;
		int ch;
		int i,j;

		if( args.length < 2 ) {
			System.out.println("Usage: java Agent -p <port>\n");
			System.exit(-1);
		}

		port = Integer.parseInt( args[1] );

		try { // open socket to Game Engine
			socket = new Socket( "localhost", port );
			in  = socket.getInputStream();
			out = socket.getOutputStream();
		}
		catch( IOException e ) {
			System.out.println("Could not bind to port: "+port);
			System.exit(-1);
		}

		try { // scan 5-by-5 wintow around current location
			while( true ) {
				for( i=0; i < 5; i++ ) {
					for( j=0; j < 5; j++ ) {
						if( !(( i == 2 )&&( j == 2 ))) {
							ch = in.read();
							if( ch == -1 ) {
								System.exit(-1);
							}
							view[i][j] = (char) ch;
						}
					}
				}
				//agent.print_view( view ); // COMMENT THIS OUT BEFORE SUBMISSION
				action = agent.get_action( view );
				out.write( action );
			}
		}
		catch( IOException e ) {
			System.out.println("Lost connection to port: "+ port );
			System.exit(-1);
		}
		finally {
			try {
				socket.close();
			}
			catch( IOException e ) {}
		}
	}
}
